The present invention relates to computer games in general and more particularly to analyzing game situations and displaying analysis results in graphical forms in a computer game.
A typical competitive computer game involves a human opponent and a computer opponent. Such competitive computer games include chess, auto racing, fantasy games, and sports games. For a game to retain the interest of the human opponent, it should be a good enough opponent that the human opponent does not win every time. Thus, there is an element of analysis required in all but the simplest competitive computer games. This analysis is done on a current game situation and might be used by the computer game to determine a next move of the computer opponent.
For example, where the game is chess, the computer game is programmed :to analyze a game situation, namely the current location of the chess pieces on the chess board and possibly also the history of moves made by the human opponent, and then make a decision as to what move to make in response to that game situation. The rules of chess constrain the analysis and responses and the computer need only decide, for each move, which of sixteen or fewer pieces to move to one of a few dozen spaces in a board constrained to only 64 distinct locations. Therefore, determining all of the possible moves is a simple matter. Of course, computer opponents in chess are difficult to program, but that is because moves must be anticipated many moves into the future.
With racing games, the computer-operated racecar or object just needs to be moved along a track quickly. With fantasy games, the possible actions can be arbitrary. Sports games and other competitive games that simulate real-world activities in a realistic way are more difficult in part because the field is not a small discrete set of positions and the game must behave as the human opponent would expect in the corresponding real-world activity.
As one example, the game of soccer involves several players and a ball that are free to move anywhere in a continuous two-dimensional space (possibly a three-dimensional space if player jumps and ball height are taken into account). Soccer strategy involves many considerations, such as trying to position players so that one player can kick the ball to a teammate without interference from a player on the opposing team. In order for a computerized soccer game played between a human opponent and a computer opponent to be interesting, the computer opponent must present a challenge to the human opponent and therefore, the computer game must perform in depth analysis of the game situation and determine how to move and manipulate the computer opponent team members to present that challenge. Preferably, the computer analysis is efficient enough that, given some limited amount of computing power available to the computer game, the game can analyze a game situation and fashion a suitable response in real-time.
In a computer game, one embodiment of the present invention provides for analyzing a game situation using states of a plurality of game elements by determining a state for each of the plurality of game elements, generating a representation of a Voronoi diagram among the game elements using at least some of the game elements as Voronoi sites and performing an analysis of the game situation using the Voronoi diagram. The analysis is a spatial analysis that might be used as the basis of a tactical analysis to determine a move of a computer-controlled entity. In a specific embodiment, the game space is a two-dimensional soccer field and the game elements are players having associated teams. The game space might be a three-dimensional game space. The game space might represent a baseball field, a basketball court or other game space besides a soccer field.
The state of a game element might include momentum, speed, direction of travel, velocity and/or team association of the game element. The analysis for a soccer field might include determining passing lanes between players of the computer-controlled team. For a soccer game analysis, multiple Voronoi diagrams might be generated, such as Voronoi diagrams for each team""s players without the goalies, diagrams for each team""s players with the goalies and diagrams for combinations of two teams"" players with and without goalies and the analyses done using the multiple Voronoi diagrams.
Other features and advantages of the invention will be apparent in view of the following detailed description and preferred embodiments.